/*
 *  Copyright 2007-2008 by Matthias Buch-Kromann <mbk.isv@cbs.dk>.
 *  *
 *  This file is part of the Open-source Dependency Toolkit (OSDT),
 *  see http://code.google.com/p/open-source-dependency-toolkit.
 *  
 *  The OSDT is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as 
 *  published by the Free Software Foundation, either version 3 of 
 *  the License, or (at your option) any later version.
 * 
 *  The OSDT is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 * 
 *  You should have received a copy of the GNU Lesser General Public 
 *  License along with the OSDT in the files COPYING and COPYING.LESSER.
 *  If not, see http://www.gnu.org/licenses.
 */

package org.osdtsystem.graphs.views;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import org.osdtsystem.exceptions.NodeNotFoundException;
import org.osdtsystem.exceptions.NonUniqueNameException;
import org.osdtsystem.graphs.Graph;
import org.osdtsystem.graphs.io.GraphIDs;
import org.osdtsystem.utils.Helper;
import org.osdtsystem.values.EdgeID;
import org.osdtsystem.values.Layer;
import org.osdtsystem.values.NodeID;

/**
 *
 * @author Matthias Buch-Kromann <mbk.isv@cbs.dk>
 */
public class DependencyAlignmentEngine implements DependencyAlignment {
    Graph graph;
    DependencyTree source, target;
    WordAlignment alignment;
    Layer treeAlignmentLayer;
    
    public DependencyAlignmentEngine(Graph graph, DependencyTree source, 
            DependencyTree target, WordAlignment alignment, String name) 
            throws NonUniqueNameException {
        this(graph, source, target, alignment, 
                graph.addLayer(name + ViewConstants.WordAlignmentSuffix));
        graph.addView(this, name);
    }
    
    public DependencyAlignmentEngine(Graph graph, DependencyTree source, 
            DependencyTree target, WordAlignment alignment, Layer treeAlignmentLayer) {
        this.graph = graph;
        this.source = source;
        this.target = target;
        this.alignment = alignment;
        this.treeAlignmentLayer = treeAlignmentLayer;
    }

    @Override
    public List<NodeID> alignments() {
        return graph.nodes(treeAlignmentLayer);
    }

    @Override
    public List<NodeID> alignments(NodeID node) {
        Set<NodeID> alignments = new HashSet<NodeID>();
        for (EdgeID edge : graph.outEdges(node, treeAlignmentLayer))
            alignments.add(graph.inNode(edge));
        return Arrays.asList(alignments.toArray(new NodeID[0]));
    }

    @Override
    public List<NodeID> nodes(NodeID alignment) {
        Set<NodeID> nodes = new HashSet<NodeID>();
        for (EdgeID edge : graph.inEdges(alignment)) {
            nodes.add(graph.outNode(edge));
        }
        return Arrays.asList(nodes.toArray(new NodeID[0]));
    }

    @Override
    public List<NodeID> sourceNodes(NodeID alignment) {
                Set<NodeID> sourceNodes = new HashSet<NodeID>();
        for (EdgeID edge : graph.inEdges(alignment)) {
            NodeID node = graph.outNode(edge);
            if (source.containsNode(node))
                sourceNodes.add(node);
        }
        return Arrays.asList(sourceNodes.toArray(new NodeID[0]));
    }

    @Override
    public List<NodeID> targetNodes(NodeID alignment) {
        Set<NodeID> targetNodes = new HashSet<NodeID>();
        for (EdgeID edge : graph.inEdges(alignment)) {
            NodeID node = graph.outNode(edge);
            if (target.containsNode(node))
                targetNodes.add(node);
        }
        return Arrays.asList(targetNodes.toArray(new NodeID[0]));
    }

    @Override
    public void setGraph(Graph graph) {
        this.graph = graph;
    }

    @Override
    public View copy() {
        return new DependencyAlignmentEngine(graph, source, target, alignment, 
                treeAlignmentLayer);
    }

    @Override
    public void clear() {
        graph.clear(treeAlignmentLayer);
    }

    public void update() {
    }

    public void update(Set<NodeID> nodes) {
        
        
    }

    /**
     * A class that computes the strongly connected components in the graph consisting 
     * of the source tree, target tree, and word alignment. The implementation is based
     * on the algorithm proposed by J. Cheriyan and K. Mehlhorn, Algorithmica (1996) 
     * 15: 521-549 (Program 4). Like Sedgewick (
     */
    public class StronglyConnectedComponents {
        int count = 0;
        Map<NodeID,Integer> dfsnum = new HashMap<NodeID,Integer>();
        Queue<NodeID> roots = new LinkedList<NodeID>();
        Queue<NodeID> unfinished = new LinkedList<NodeID>();
        Set<NodeID> inUnfinished = new HashSet<NodeID>();
                
        public void compute() {
            // Reset all stacks and counters
            count = 0;
            dfsnum.clear();
            roots.clear();
            unfinished.clear();
            inUnfinished.clear();
            
            // Find all nodes in graph
            List<NodeID> nodes = new ArrayList<NodeID>();
            nodes.addAll(source.nodes());
            nodes.addAll(target.nodes());
            nodes.addAll(alignment.alignments());
           
            // Visit all nodes
            for (NodeID node : nodes) {
                if (! dfsnum.containsKey(node))
                    depthFirstSearch(node);
            }
        }
        
        private List<NodeID> children(NodeID v)  {
            Set<NodeID> children = new HashSet<NodeID>();
            
            // Children in source and target tree
            for (EdgeID e : source.dependentEdges(v))
                children.add(source.dependent(e));
            for (EdgeID e : target.dependentEdges(v))
                children.add(target.dependent(e));
            
            // Children in alignment layer
            for (NodeID a : alignment.alignments(v)) {
                children.addAll(alignment.sourceNodes(a));
                children.addAll(alignment.targetNodes(a));
            }
            
            // Remove v
            children.remove(v);
            
            // Return nodes
            return Arrays.asList(children.toArray(new NodeID[0]));
        }
        
        private void depthFirstSearch(NodeID v) {
            // Record node as visited by the depth-first search
            dfsnum.put(v, ++count);
            unfinished.add(v);
            inUnfinished.add(v);
            roots.add(v);
            
            // Recursively visit all nodes that can be reached from v
            for (NodeID w : children(v)) {
                if (! dfsnum.containsKey(w)) {
                    depthFirstSearch(w);
                } else if (inUnfinished.contains(w)) {
                    // Merge components
                    while (dfsnum.get(roots.peek()) > dfsnum.get(w)) {
                        roots.remove();
                    }
                }
            }

            // Read off the component
            if (v == roots.peek()) {
                NodeID w = null;
                while (v != w) {
                    // w is an element of the scc with root v
                    w = unfinished.remove();
                    inUnfinished.remove(w);
                }
                roots.remove();
            }
        }
    }
    
    public void computeSCC() {
        
    }
    
    private void dfsSCC(NodeID node) {
        
    }

    @Override
    public void recompute() {
        // TODO
        // throw new UnsupportedOperationException("Not supported yet.");
    }

    @Override
    public String toOSDT(Graph graph, GraphIDs ids) {
        return "DependencyAlignmentEngine(VIEW" + ids.id(source)
                + ",VIEW" + ids.id(target) 
                + ",VIEW" + ids.id(alignment)
                + ",LAYER" + ids.id(treeAlignmentLayer) + ")";
    }

    public static View fromOSDT(Graph graph, GraphIDs ids, String specification) {
        throw new UnsupportedOperationException("Not yet implemented");
    }

    public List<List<NodeID>> lpaDependencyAlign() {
        // Assign base products to source and target nodes on word alignment edges: 
        // an m-n edge is assigned a prime p. Each source node is assigned the same
        // product p^k where k=lcm(m,n)/m for the m source nodes, k=lcm(m,n)/n for 
        // the n target nodes. If m=0 or n=0, we always set k=1 for all nodes.
        Map<NodeID,BigInteger> baseProducts = lpaBaseProducts();
        
        // Assign products to all nodes in the source and target tree
        Map<NodeID,BigInteger> products = new HashMap<NodeID,BigInteger>();
        Map<BigInteger,List<NodeID>> productsReverse = new HashMap<BigInteger,List<NodeID>>();
        lpaCompositeProducts(source, baseProducts, products, productsReverse);
        lpaCompositeProducts(target, baseProducts, products, productsReverse);
        
        // Find all nodes with identical products. Pick the lowest source and target
        // node as the two heads of the unit.
        List<List<NodeID>> pairs = new ArrayList<List<NodeID>>();
        for (List<NodeID> nodes : productsReverse.values()) {
            NodeID snode = lpaLowestNode(nodes, source);
            NodeID tnode = lpaLowestNode(nodes, target);
            if (snode != null && tnode != null) {
                NodeID[] pair = { snode, tnode };
                pairs.add(Arrays.asList(pair));
            }
        }
        
        // Return the list of source-target node pairs
        return pairs;
    }

    private Map<NodeID, BigInteger> lpaBaseProducts() {
        // Generate a prime for each alignment node
        List<NodeID> alignmentNodes = alignments();
        List<Integer> primes = Helper.primes(alignmentNodes.size());
        int primeCounter = 0;
        
        // Process all alignment nodes in the alignment
        Map<NodeID,BigInteger> baseProducts = new HashMap<NodeID,BigInteger>();
        for (NodeID alignmentNode : alignments()) {
            // Find source and target node lists
            List<NodeID> snodes = sourceNodes(alignmentNode);
            List<NodeID> tnodes = targetNodes(alignmentNode);
            int sn = snodes.size();
            int tn = tnodes.size();
            int gcd = Helper.greatestCommonDivisor(sn, tn);
            
            // Assign prime power to alignment
            BigInteger prime = BigInteger.ONE;
            BigInteger spower = BigInteger.ONE;
            BigInteger tpower = BigInteger.ONE;
            if (sn != 0 && tn != 0) {
                prime = BigInteger.valueOf(primes.get(primeCounter++));
                spower = prime.pow(tn / gcd);
                tpower = prime.pow(sn / gcd);
            }
            
            // Store assigned power for all nodes
            for (NodeID snode : snodes) 
                baseProducts.put(snode, baseProducts.containsKey(snode) 
                    ? baseProducts.get(snode).multiply(spower)
                    : spower);
            for (NodeID tnode : tnodes) 
                baseProducts.put(tnode, baseProducts.containsKey(tnode) 
                    ? baseProducts.get(tnode).multiply(tpower)
                    : tpower);
        }
        return baseProducts;
    }

    private void lpaCompositeProducts(DependencyTree tree, 
            Map<NodeID, BigInteger> baseProducts, 
            Map<NodeID, BigInteger> products, 
            Map<BigInteger, List<NodeID>> productsReverse) {
        for (NodeID node : tree.nodes())
            if (! products.containsKey(node))
                lpaCompositeProductsDepthFirst(node, tree, baseProducts, products, productsReverse);
    }

    private BigInteger lpaCompositeProductsDepthFirst(NodeID node, 
            DependencyTree tree, 
            Map<NodeID, BigInteger> baseProducts, 
            Map<NodeID, BigInteger> products, 
            Map<BigInteger, List<NodeID>> productsReverse) {
        // Return value associated with node if it has been visited already
        if (products.containsKey(node))
            return products.get(node);
        
        // First-time visit, so initially set its product to the base number, thereby
        // marking that is has been visited now. 
        BigInteger product = baseProducts.get(node);
        if (product == null) 
            product = BigInteger.ONE;
        products.put(node, product);
        
        // Visit child nodes
        for (NodeID child : tree.dependents(node))
            product = product.multiply(lpaCompositeProductsDepthFirst(child, 
                    tree, baseProducts, products, productsReverse));
        
        // Ensure product exists in reverse table
        products.put(node, product);
        List<NodeID> list = productsReverse.get(product);
        if (list == null) 
            productsReverse.put(product, list = new ArrayList<NodeID>());
        
        // Add node to reverse table
        list.add(node);
        
        // Return product
        return product;
    }

    private NodeID lpaLowestNode(List<NodeID> nodes, DependencyTree tree) {
        NodeID minNode = null;
        int minHeight = 0;
        for (NodeID node : nodes) {
            if (tree.containsNode(node)) {
                int height;
                try {
                    height = tree.height(node);
                    if (minNode == null || minHeight > height) {
                        minHeight = height;
                        minNode = node;
                    }
                } catch (NodeNotFoundException ex) {
                    // Shouldn't happen: ignore it if it does
                }
            }
        }
        return minNode;
    }

    private void lpaMultiplyProduct(NodeID node, BigInteger multiplier, 
            Map<NodeID,BigInteger> products, Map<BigInteger,List<NodeID>> reverse) {
        BigInteger product = products.get(node);
        product = (product != null) ? product.multiply(multiplier) : multiplier;
        products.put(node, product);
        
    }


}